<script>
  console.log(3 >> 1);
  //   给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

  //   正数的平方根有两个，只输出其中的正数平方根。

  //   如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

  //   来源：力扣（LeetCode）
  //   链接：https://leetcode.cn/problems/jJ0w9p

  //   示例 1:

  //   输入: x = 4
  //   输出: 2

  //   示例 2:

  //   输入: x = 8
  //   输出: 2
  //   解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2

  /**
   * 二分查找
   * 取中间值的平方根 不断与之比较
   * 缩小边界就是最终结果
   * 0 的结果 返回 0
   *
   * Math.sqrt() 向下取整也可以拿到相同结果
   */
  /**
   * @param {number} x
   * @return {number}
   */

  var mySqrt = function (x) {
    if (x == 0) return 0;
    let left = 1,
      right = x;

    while (left <= right) {
      // 防止溢出
      let mid = left + ((right - left) >> 1);
      // 判断mid平方 是否小于等于 x
      if (mid <= x / mid) {
        // 判断mid + 1的平方是否大于x 如果mid+1的平方大于x 那么mid就是x的平方根
        if (mid + 1 > x / (mid + 1)) {
          return mid;
        }
        // 小于 说明x的平方根比mid大 缩小left的范围 left mid+1
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  };
</script>
